059 - Many Graph Queries（★7）

解説AC

愚直にやっていいならdp(i,j)=頂点iからjまで辿り着けるか？　というBool値のDPを行えばよい。

bitsetで定数倍高速化を行う。基本的にはdp(j)|=dp(i) を頂点番号の小さい方から行うことでできる。

100000*100000bit持つとメモリ制限に収まらないため、平方分割の要領で始点を320頂点ごとにまとめて計算する。始点を0~319,320~639,..., のように分類し、DPをこの上でまとめて行う。クエリのうち始点がこの範囲に収まっているものだけを解答する。

こういうの相当苦手かもしれない